// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态
// 3. 初始化：保证填表时不越界
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 结合滚动数组优化 - 注意赋值顺序

// 经典题目：斐波那契数列模型


// 例题 3：
// 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
//
//        你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
//
//        请你计算并返回达到楼梯顶部的最低花费。
//
//        示例 1：
//
//        输入：cost = [10,15,20]
//        输出：15
//        解释：你将从下标为 1 的台阶开始。
//        - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
//        总花费为 15 。
//        示例 2：
//
//        输入：cost = [1,100,1,1,1,100,1,1,100,1]
//        输出：6
//        解释：你将从下标为 0 的台阶开始。
//        - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
//        - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
//        - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
//        - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
//        - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
//        - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
//        总花费为 6 。
//
//
//        提示：
//
//        2 <= cost.length <= 1000
//        0 <= cost[i] <= 999

// 解题思路 1：
// dp[i] 表示到达 i 台阶的最小花费
// dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]
// dp[0] = cost[0], dp[1] = cost[1]
// 从左往右填表
// 返回 Math.min(dp[n - 1], dp[n - 2])

// 解题思路 2：
// dp[i] 表示从 i 出发到达楼顶的最小花费
// dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i]
// dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]
// 从右往左填表
// 返回 Math.min(dp[0], dp[1])

public class MinCostClimbingStairs {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];

        dp[0] = cost[0];
        dp[1] = cost[1];

        for(int i = 2; i < n; i++){
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }

        return Math.min(dp[n - 1], dp[n - 2]);
    }

    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;

        int[] dp = new int[n];

        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];

        for(int i = n - 3; i >= 0; i--){
            dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
        }

        return Math.min(dp[0], dp[1]);
    }
}
